// https://leetcode.cn/problems/last-stone-weight/

// 题干：有一堆石头，每块石头的重量都是正整数。
//      每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
//      如果 x == y，那么两块石头都会被完全粉碎；
//      如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
//      最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

// 示例：输入：[2,7,4,1,8,1]
//      输出：1

// 碎语：简单的模拟题，每次都挑选重量最大的两个石头，使用优先级队列来解决问题

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int lastStoneWeight(vector<int>& stones)
    {
        // 1.创建一个大根堆
        priority_queue<int> heap;

        // 2.将所有元素丢进这个堆里面
        for (const auto& num : stones) heap.push(num);

        // 3.模拟这个过程
        while (heap.size() > 1){
            int a = heap.top() ; heap.pop();
            int b = heap.top() ; heap.pop();

            if (a > b) heap.push(a - b);
        }

        return heap.size() ? heap.top() : 0;
    }
};

int main()
{
    Solution sol;
    vector<int> stones = {2,7,4,1,8,1};

    cout << sol.lastStoneWeight(stones) << endl;

    return 0;
}